package Solution;

import java.util.Arrays;

import Data.ListNode;

//1排序的数据是整数->泛型
//2数据存储在数组中
//3数据最后以升序排列->接口

//归并排序和快速排序都采用分治法；归并排序的主要工作是将两个子数组进行归并（在子数组排序完成后）；快速排序的主要工作是将数组划分为两个子数组（在子数组排序完成前）
//归并排序在归并两个子数组是需要一个临时数组，快速排序不需要，->快速排序的空间效率优与归并排序


public class Sort {
	private static int sum;

	public int getSum() {
		return sum;
	}

	public void setSum(int sum) {
		this.sum = sum;
	}

	public Sort() {
		this.sum = 0;
	}

	// 冒泡排序:多次遍历数组；每次遍历中，比较相邻元素，若逆序则交换；
	// 1第k次遍历，不需要考虑后k-1个元素
	// 2若某次遍历无元素交换，则不必进行下一次遍历
	// 3最佳：1次遍历(数组以排序好);最差：n(n-1)/2(数组逆序);O(n^2)
	public static void BulleSort(int[] numbers) {
		sum = 0;
		boolean flag = true;
		for (int i = 1; i < numbers.length && flag; i++) {
			flag = false;
			for (int j = 0; j < numbers.length - i; j++) {
				if (numbers[j] > numbers[j + 1]) {
					int temp = numbers[j + 1];
					numbers[j + 1] = numbers[j];
					numbers[j] = temp;
					flag = true;
					sum++;
				}
			}
		}
	}

	// 归并排序：数组分为两半，对每部分递归地应用归并排序，在两部分排好序后，对他们进行归并
	// T(n):n个元素排序所需时间，设n=2^k,
	// 则T(n)=T(n/2)+T(n/2)+mergeTime=O(n*log(n))
	// mergeTime=2*n-1(n-1:比较两个长度为n/2子数组的最多次数，n:移动元素到临时数组(固定))
	// Arrays.sort();采用归并排序

	// list1,list2已经排好序
	public static int[] merge(int[] list1, int[] list2) {
		int[] result = new int[list1.length + list2.length];

		int p1, p2, pr;
		p1 = 0;
		p2 = 0;
		pr = 0;
		while (p1 < list1.length && p2 < list2.length) {
			if (list1[p1] < list2[p2]) {
				result[pr++] = list1[p1++];
			} else {
				result[pr++] = list2[p2++];
			}
		}
		while (p1 < list1.length) {
			result[pr++] = list1[p1++];
		}
		while (p2 < list2.length) {
			result[pr++] = list2[p2++];
		}
		return result;
	}

	// System提供了一个静态方法arraycopy(),我们可以使用它来实现数组之间的复制。其函数原型是： public static void
	// arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
	// src:源数组； srcPos:源数组要复制的起始位置； dest:目的数组； destPos:目的数组放置的起始位置；
	// length:复制的长度。 注意：src and dest都必须是同类型或者可以进行转换类型的数组．
	// 有趣的是这个函数可以实现自己到自己复制，比如： int[] fun ={0,1,2,3,4,5,6};
	// System.arraycopy(fun,0,fun,3,3); 则结果为：{0,1,2,0,1,2,6};
	// 实现过程是这样的，先生成一个长度为length的临时数组,将fun数组中srcPos
	// 到srcPos+length-1之间的数据拷贝到临时数组中，再执行System.arraycopy(临时数组,0,fun,3,3).
	public static void mergeSort(int[] numbers) {
		if (numbers.length > 1) {
			int[] head = new int[numbers.length / 2];
			System.arraycopy(numbers, 0, head, 0, numbers.length / 2);
			mergeSort(head);

			int[] tail = new int[numbers.length - numbers.length / 2];
			System.arraycopy(numbers, numbers.length / 2, tail, 0,
					numbers.length - numbers.length / 2);
			mergeSort(tail);

			int[] result = merge(head, tail);
			// return result;
			System.arraycopy(result, 0, numbers, 0, result.length);
		}
		// return numbers
	}

	// 快速排序：在数组中选择一个主元的元素，将数组分为两部分，使得第一部分的所有元素小于等于主元，第二部分的所有元素都大于主元；
	// 对得到的两部分分别递归地调用排序算法
	// 最差情况（序列正序或逆序）：划分n个元素需要n次比较和那次移动，得到一个大的子数组（上次划分的子数组的规模减去1）和一个空数组，共需要（n-1）+(n-2)+...+2+1=n(n-1)/2;
	// 最佳情况（第一个主元是序列的中间值）：每次主元将数组分为大致相等的两部分，则T(n)=T(n/2)+T(n/2)+n=O(n*log(n))

	public static void quickSort(int[] numbers, int first, int last) {
		if (last > first) {
			int pivotIndex = partition(numbers, first, last);
			quickSort(numbers, first, pivotIndex - 1);
			quickSort(numbers, pivotIndex + 1, last);
		}
	}

	private static int partition(int[] numbers, int first, int last) {// 确认主元的位置
		int pivot = numbers[first];// 每次取第一个元素作为主元
		int low = first;
		int high = last;
		int temp;
		while (high > low) {
			while (low < high && numbers[high] >= pivot) { // 先判断high指针在判断low指针
				high--;
			}
			temp = numbers[high];
			numbers[high] = numbers[low];
			numbers[low] = temp;
			while (low < high && numbers[low] <= pivot) {
				low++;
			}
			temp = numbers[high];
			numbers[high] = numbers[low];
			numbers[low] = temp;
		}

		return low;
	}

	public static void show(int[] numbers) {
		for (int i = 0; i < numbers.length; i++) {
			System.out.println(i + ":" + numbers[i]);
		}
		System.out.println("sum:" + sum);
	}

	public static void main(String[] args) {
		int[] test = { 4, 3, 2, 1 };
		// BulleSort(test);
		// mergeSort(test);
		quickSort(test, 0, test.length - 1);
		show(test);
	}

}
